Section: New Results

Distributed average consensus algorithms

Finite-time average consensus protocols

Participants : A. Kibangou [Contact person] , D. Tran.

Nowadays, several distributed estimation algorithms are based on the average consensus concept. Average consensus can be reached using a linear iterations scheme where each node repeatedly updates its value as a weighted linear combination of its own value and those of its neighbors. The main benefit of using a linear iterations scheme is that, at each time-step, each node only has to transmit a single value to each of its neighbors. Based on such a scheme, several algorithms have been proposed in the literature. However, in the majority of the proposed algorithms the weights are chosen so that all the nodes asymptotically converge to the same value. Sometimes, consensus can be embedded as a step of more sophisticated distributed. Obviously, asymptotic convergence is not suitable for these kinds of distributed methods. Therefore, it is interesting to address the question of exact consensus in finite-time. For time-invariant network topologies and in the perfect information exchange case, i.e. without channel noise nor quantization, we have shown that the finite-time average consensus problem can be solved as a matrix factorization problem with joint diagonalizable matrices depending on the Graph Laplacian eigenvalues [40] , [39] . Moreover, the number of iterations is equal to the number of distinct nonzero eigenvalues of the graph Laplacian matrix. The design of such a protocol requires the knowledge of the Laplacian spectrum, which can be carried out in a distributed way (see [65] , [73] , [76] ). In [77] , the matrix factorization problem is solved in a distributed way. In particular a learning method was proposed and the optimization problem was solved by means of distributed gradient backpropagation algorithms. Unlike the method in [40] , the factor matrices are not necessarily symmetric and the number of these factor matrices is exactly equal to the diameter of the graph.

Quadratic indices for performance evaluation of consensus algorithms

Participants : F. Garin [Contact person] , S. Zampieri [Università di Padova] , E. Lovisari [Università di Padova and Lund Univ.] .

Traditional analysis of linear average-consensus algorithms studies, for a given communication graph, the convergence rate, given by the essential spectral radius of the transition matrix (i.e., the second largest eigenvalues' modulus). For many graph families, such analysis predicts a performance which degrades when the number of agents grows, basically because spreading information across a larger graph requires a longer time. However, when considering other well-known quadratic performance indices (involving all the eigenvalues of the transition matrix), the scaling law with respect to the number of agents can be different. This is consistent with the fact that, in many applications, for example in estimation problems, it is natural to expect that a larger number of cooperating agents has a positive, not a negative effect on performance. It is natural to use a different performance measure when the algorithm is used for different purposes, e.g., within a distributed estimation or control algorithm. Examples of various relevant costs can be found in the book chapter [66] and in the references therein.

We are interested in evaluating the effect of the topology of the communication graph on performance, in particular for large-scale graphs. Motivated by the study of wireless sensor networks, our main objective is to understand the limitations which arise when agents are limited to truly local interactions, i.e., the neighborhoods are determined by being `near' in a geometric (Euclidean) way, differently from graphs with few but possibly `distant' connections, such as in small world models. At first [19] we consider graphs which are regular lattices (infinite lattices, or grids on tori, or grids on hyper-cubes), which are examples of geometrically local interactions, but also have a very rich structure: their symmetries allow to exploit powerful algebraic tools, such as the discrete Fourier transform over rings, to compute their eigenvalues, and then find bounds on the associated costs. Then, we extend the results to a more general class of graphs, thus showing that the behavior of lattices is mainly due to the local nature of interactions and not to the spatial invariance (the richness of the automorphism group). To do so, we exploit the analogy between reversible Markov chains and resistive electrical networks, which allows to study some perturbed grids, with less regularity but still exhibiting the same dimension-dependent asymptotic behavior. This latter work is part of the Ph.D. thesis of E. Lovisari at University of Padova, Italy, and the topic of a journal paper in preparation.